import java.util.Arrays;

public class leetcode977_有序数组的平方 {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = new int[] {-4,-1,0,3,10};
        Arrays.stream(s.sortedSquares(nums)).forEach(System.out::println);
    }
}


class Solution {
    /*
    * 双指针，i指向数组开始，j指向数组结束
    * */
    public int[] sortedSquares(int[] nums) {
        // 创建一个和输入数组相同大小的新数组，用于存放结果
        int[] ans = new int[nums.length];

        // 双指针，i指向数组开始，j指向数组结束，pos决定新数组插入的位置，默认为从数组末端网前插入，保证新数组为递增排序
        int i = 0, j = nums.length - 1, pos = nums.length - 1;

        while (i <= j) {
            if (nums[j] * nums[j] > nums[i] * nums[i]) {
                ans[pos--] = nums[j] * nums[j];
                j--;
            } else {
                ans[pos--] = nums[i] * nums[i];
                i++;
            }
        }
        return ans;
    }
}